//
//  BothWayLinkList.swift
//  DataStructureAndAlgorithm
//
//  Created by icemelon on 2021/7/15.
//



import Foundation


/// 双向链表
class BothWayLinkList<E: Equatable> {
    var count: Int = 0
    var first: Node<E>? = nil  //默认为空
    var last: Node<E>? = nil  //默认为空
    
    let ElEMENT_NOT_FOUND = -1
    
    class Node<E>: CustomStringConvertible {
        var element: E!
        var next: Node<E>?
        weak var prev: Node<E>?
        init(element: E, prev: Node<E>?, next: Node<E>?) {
            self.element = element
            self.prev = prev
            self.next = next
        }
        var description: String {
            get {
                return "prev:" + (prev?.element.debugDescription ?? "nil") +
                    "-element:" + (element.debugDescription) +
                "-next:" + (next?.element.debugDescription ?? "nil")
            }
        }
    }
    
    func isEmpty() -> Bool {
        return count == 0
    }
    
    func contains(element: E) -> Bool {
        return indexOfElement(element: element) != ElEMENT_NOT_FOUND
    }
    
    /// index节点位置的对象
    /// - Parameter index: <#index description#>
    /// - Returns: <#description#>
    func getNode(at index: Int) -> Node<E>? {
        guard rangeCheck(index: index) else { return nil }
        if index < (count >> 1) {
            var node = first
            for _ in 0..<index {
                node = node?.next!
            }
            return node
        }
        else {
            var node = last
            var i = count - 1
            while i > index, node?.prev != nil {
                node = node?.prev!
                i -= 1
            }
            return node
        }
    }

    func indexOfElement(element: E) -> Int {
        for i in 0..<count {
            let node = getNode(at: i)
            if node?.element == element {
                return i
            }
        }
        return ElEMENT_NOT_FOUND
    }
    
    
    /// 检测index是否越界
    /// - Parameter index: 传进来的下标
    /// - Returns: true false
    func rangeCheck(index: Int) -> Bool {
        guard index >= 0, index < count else {
            return false
        }
        return true
    }
   
}

extension BothWayLinkList {
    func add(element: E) {
        add(index: count, element: element)
    }
    
    func add(index: Int, element: E) {
        if index == 0 {
            let new = Node(element: element, prev: nil, next: first)
            if index == count {
                last = new
            }
            else {
                first?.prev = new
            }
            first = new
            count += 1
        }
        else {
            if let pre = getNode(at: index - 1) {
                let new = Node(element: element, prev: pre, next: pre.next)
                pre.next?.prev = new
                pre.next = new
                if index == count {
                    last = new
                }
                count += 1
            }
        }
    }
    
    func remove(element: E) {
        let index = indexOfElement(element: element)
        remove(at: index)
    }
    
    func remove(at index: Int) {
        if index == 0 {
            if count > 0 {
                count -= 1
                if count == 0 {
                    first = nil
                    last = nil
                }
                else {
                    let tmp = first?.next
                
                    first?.next = nil
                    tmp?.prev = nil
                    first = tmp
                }
            }
        }
        else {
            if let pre = getNode(at: index - 1) {
                if index == count - 1 {
                    pre.next = nil
                    pre.next?.prev = nil
                    last = pre
                }
                else {
                    pre.next?.next?.prev = pre
                    pre.next = pre.next?.next
                }
                count -= 1
            }   
        }
    }
    
    func removeAll() {
        count = 0
        first = nil
        last = nil
    }
    
    @discardableResult func replace(at index: Int, element: E) -> E? {
        guard rangeCheck(index: index) else {
            return nil
        }
        let originalNode = getNode(at: index)
        let old = originalNode?.element
        originalNode?.element = element
        return old
    }
}

extension BothWayLinkList: CustomStringConvertible {
    var description: String {
        get {
            var str = "链表开始first\n"
            for i in 0..<count {
                let node = getNode(at: i)
                str += "->"
                str += "("
                str += (node?.prev?.element.debugDescription) ?? "nil        " + "-"
                str += (node?.element.debugDescription) ?? "nil" + "-"
                str += (node?.next?.element.debugDescription) ?? "nil        "
                str += ")" + "\n"
            }
            str += "->last"
            return str
        }
    }
}
